package com.yaoli.ajob;

import java.math.BigInteger;

/**
 * Created by will on 2017/4/16.
 */
public class _306_AdditiveNumber {
    public static void main(String[] args) {
        _306_AdditiveNumber additiveNumber = new _306_AdditiveNumber();
        System.out.println(additiveNumber.isAdditiveNumber("1023"));
        //System.out.println(additiveNumber.isAdditiveNumber("0"));
    }

    public boolean isAdditiveNumber(String num) {
        if(num.length() < 3){
            return false;
        }else{
            return calc(num);
        }
    }

    public boolean calc(String num){
        if(num.length() <= 2){
            return true;
        }

        boolean flag = false;

        for (int i = 0; i < num.length() - 2; i++) {
            if(num.charAt(0) == '0' ) break;

            //numA Over,numB begin
            for (int j = i + 1; j < num.length(); j++) {
                if(num.charAt(0) == '0' ) break;

                //numB Over
                for (int k = j + 1; k < num.length(); k++) {
                    if(num.charAt(0) == '0' ) break;

                    if(calc(i,j,k,num) == true){
                        flag = true;
                        break;
                    }

                }

                if(flag == true){
                    break;
                }

            }

            if(flag == true){
                break;
            }
        }

        return flag;
    }


    public boolean calc(int num1begin,int num2begin,int num2end,String num){
        if(num2end > num.length()){
            return true;
        }
        BigInteger num1 = new BigInteger(num.substring(num1begin,num2begin));

        BigInteger num2 = new BigInteger(num.substring(num2begin,num2end));

        String res = num1.add(num2).toString();

        String remain = num.substring(num2end);

        boolean flag = true;

        for (int i = 0; i < res.length() && i < remain.length() ; i++) {
            if(res.charAt(i) != remain.charAt(i)){
                flag = false;
                break;
            }
        }

        if(flag == false){
            return false;
        }else{
            if(remain.length() == res.length()){
                return true;
            }
            return calc(num.substring(num2begin));
        }
    }
}
